package codetop.microsoft.T103;

import util.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-08-17 9:58:12 星期三
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if (root == null)
            return results;
        Deque<TreeNode> q = new LinkedList<>();
        Deque<Integer> qLevel = new LinkedList<>();
        q.offer(root);
        qLevel.offer(0);
        while (!q.isEmpty()) {
            int size = q.size();
            int level = qLevel.poll();
            qLevel.offer(level + 1);
            List<Integer> result = new ArrayList<>();
            for (int i=0; i<size; ++i) {
                if (level % 2 == 0) {
                    TreeNode front = q.removeFirst();
                    result.add(front.val);
                    if (front.left != null)
                        q.addLast(front.left);
                    if (front.right != null)
                        q.addLast(front.right);
                } else {
                    TreeNode tail = q.removeLast();
                    result.add(tail.val);
                    if (tail.right != null)
                        q.addFirst(tail.right);
                    if (tail.left != null)
                        q.addFirst(tail.left);
                }
            }
            results.add(result);
        }
        return results;
    }
}